package study;

/**
 * 判断回文字符串
 * 单链表存储
 */
public class PalindromeString {

    public static void main(String[] args) {
        Node node = build('a', 'b', 'c', 'b', 'b', 'c', 'b', 'a');
        System.out.println(test(node));

        if(node != null)
            do {
                System.out.print(node.value);
                if(node.next == null)
                    break;
                System.out.print(" -> ");
                node = node.next;
            } while(true);
    }

    public static boolean test(Node node) {
        Node middle, r, limit; //中间节点，要开始比较的右节点，最右节点
        if((middle = limit = node) == null)
            return false;
        if((r = node.next) == null)
            return true;
        boolean even = false;
        while(limit.next != null) { // 找出中间节点，和是基数还是偶数?
            limit = limit.next;
            if(limit.next == null) {
                even = true;
                break;
            }
            limit = limit.next;

            Node t = middle; // 将左边反转
            middle = r;
            r = middle.next;
            middle.next = t;
            if(t.next == middle)
                t.next = null;
        }

        if(limit == r) {
            if(node.next != limit) { // 说明是3个元素，恢复链表
                node.next = middle;
                middle.next = limit;
            }
            return r.value == node.value;
        }

        Node c;
        if(!even) {
            c = middle.next;
            middle.next = r;
        } else {
            c = middle;
            middle = r;
        }

        while(c != null) { // 检查左边和右边
            if(c.value != r.value)
                return false;

            Node t = c; // 恢复左边的链表
            c = c.next;
            t.next = middle;
            middle = t;
            r = r.next;
        }
        return true;
    }

    private static Node build(char... chars) {
        Node prev = null;
        for (int i = chars.length - 1; i >= 0; i --) {
            prev = new Node(chars[i], prev);
        }
        return prev;
    }

    private static class Node {
        char value;
        Node next;

        public Node(char value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}
